package LinkedList;

import LinkedList.Supple.ListNode;

import java.util.HashSet;

/**
 * @Author: 吕庆龙
 * @Date: 2020/7/16 12:23
 * <p>
 * 功能描述:
 */
public class JZ_056 {

    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) {
            return null;
        }
        // 先找出相同结点，存入 set
        HashSet<Integer> set = new HashSet<>();
        ListNode pre = pHead;
        ListNode cur = pHead.next;
        while (cur != null) {
            if (cur.val == pre.val) {
                set.add(cur.val);
            }
            pre = cur;
            cur = cur.next;
        }

        ListNode vhead = new ListNode(-1);
        vhead.next = pHead;
        pre = vhead;
        cur = pHead;
        while (cur != null) {
            if (set.contains(cur.val)) {
                cur = cur.next;
                pre.next = cur;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return vhead.next;
    }
}
